#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int MinLen = INT_MAX;
        for (int i = 0; i < strs.size(); i++)
            MinLen = min(MinLen, (int)strs[i].size());
        int pub_len = 0;
        while (pub_len < MinLen) {
            char ch = strs[0][pub_len];
            for (int i = 1; i < strs.size(); i++) {
                if (ch != strs[i][pub_len]) {
                    return strs[0].substr(0, pub_len);
                }
            }
            pub_len++;
        }
        return strs[0].substr(0, pub_len);
    }
};

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size();
        int ans_len = 0;
        int ans_left = 0;
        for (int i = 0; i < len; i++) {
            int left = i - 1, right = i + 1;
            int lenCur = 1;
            while (left >= 0 && right <= len && s[left] == s[right]) {
                left--;
                right++;
                lenCur += 2;
            }
            if (ans_len < lenCur) {
                ans_len = lenCur;
                ans_left = left + 1;
            }
            left = i, right = i + 1;
            lenCur = 0;
            while (left >= 0 && right <= len && s[left] == s[right]) {
                left--;
                right++;
                lenCur += 2;
            }
            if (ans_len < lenCur) {
                ans_len = lenCur;
                ans_left = left + 1;
            }
        }
        return s.substr(ans_left, ans_len);
    }
};


class Solution {
public:
    string addBinary(string a, string b) {
        string arr1(a.rbegin(), a.rend());
        string arr2(b.rbegin(), b.rend());
        string ans;
        int len_max = max(a.size(), b.size()) + 5;
        arr1.resize(len_max, '0');
        arr2.resize(len_max, '0');
        ans.reserve(len_max);
        int k = 0;
        for (int i = 0; i < len_max - 2; i++) {
            k += (arr1[i] + arr2[i] - '0' - '0');
            ans.push_back(k % 2 + '0');
            k /= 2;
        }
        int i;
        for (i = len_max; i >= 0 && ans[i] != '1'; i--);
        if (i == -1) return "0";
        ans.resize(i + 1);
        return string(ans.rbegin(), ans.rend());
    }
};

class Solution {
public:
    string multiply(string num1, string num2) {
        int larr[205] = { 0 };
        int rarr[205] = { 0 };
        int size1 = num1.size();
        int size2 = num2.size();
        for (int i = 0; i < size1; i++)larr[i] = num1[size1 - i - 1] - '0';
        for (int i = 0; i < size2; i++)rarr[i] = num2[size2 - i - 1] - '0';
        int ans_arr[1005] = { 0 };
        for (int i = 0; i < size1; i++) {
            for (int j = 0; j < size2; j++) {
                ans_arr[i + j] += larr[i] * rarr[j];
            }
        }
        for (int i = 0; i < 1000; i++) {
            ans_arr[i + 1] += ans_arr[i] / 10;
            ans_arr[i] %= 10;
        }
        int rem = 1000;
        while (rem >= 0 && ans_arr[rem] == 0)rem--;
        // if(rem<0)return string("");
        string str;
        while (rem >= 0) {
            str += ans_arr[rem] + '0';
            --rem;
        }
        if (str.size() == 0)str += '0';
        return str;
    }
};